package graph.undirectedgraph.adjacencymultilist;

import graph.inter.CustGraph;

import java.util.Scanner;

/**
 * 无向图 -- 邻接多重表
 */
public class AdjacencyMultiList implements CustGraph {

    // 顶点数组
    private AdjVexNode[] vexs;
    // 顶点数
    private int numVertexes;
    // 边数
    private int numEdges;
    // 访问标志数组
    private boolean[] visited;

    private Scanner sc;

    @Override
    public void createGraph() {
        System.out.println("输入图的顶点数：");
        numVertexes = sc.nextInt();
        vexs = new AdjVexNode[numVertexes];
        visited = new boolean[numVertexes];
        System.out.println("输入图的边数");
        numEdges = sc.nextInt();
        System.out.println("输入图的顶点：");
        for (int i = 0; i < numVertexes; i++) {
            String s = sc.next();
            vexs[i] = new AdjVexNode(s);
        }
        for (int i = 0; i < numVertexes; i++) {
            System.out.print(i + "." + vexs[i].getData() + "     ");
        }
        System.out.println();
        for (int k = 0; k < numEdges; k++) {
            System.out.println("输入边（vi,vj）上的下标i,下标j:");
            int i = sc.nextInt();
            int j = sc.nextInt();
            if (!edgeExist(i, j)) {
                AdjEdgeNode temp = new AdjEdgeNode(i, vexs[i].getFirstEdge(), j, vexs[j].getFirstEdge());
                vexs[i].setFirstEdge(temp);
                vexs[j].setFirstEdge(temp);
            }
        }
    }

    @Override
    public int locateVex(String u) {
        for (int i = 0; i < vexs.length; i++) {
            if (vexs[i].equals(u)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String getVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }
        return vexs[v].getData();
    }

    @Override
    public void putVex(int v, String value) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        vexs[v].setData(value);
    }

    @Override
    public String firstAdjVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }

        return null;
    }

    @Override
    public String nextAdjVex(int v, int w) {
        return null;
    }

    @Override
    public void insertVex(String v) {

    }

    @Override
    public void deleteVex(String v) {

    }

    @Override
    public void insertArc(int v, int w) {

    }

    @Override
    public void deleteArc(int v, int w) {

    }

    @Override
    public void dfsTraverse(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
    }

    @Override
    public void bfsTraverse(int v) {

    }

    /**
     * 深度优先遍历算法
     *
     * @param v 开始遍历的节点
     */
    private void depthFirstSearch(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
    }

    public boolean edgeExist(int i, int j) {
        AdjEdgeNode p = vexs[i].getFirstEdge();
        while (p != null) {
            if ((p.getIvex() == i && p.getJvex() == j)
                    || (p.getJvex() == i && p.getIvex() == j)) {
                return true;
            }
            p = p.getIvex() == i ? p.getIlink() : p.getJlink();
        }
        return false;
    }
}
